284. Peeking Iterator
Medium

Design an iterator that supports the peek operation on a list in addition to the hasNext and the next operations.

Implement the PeekingIterator class:

  • PeekingIterator(int[] nums) Initializes the object with the given integer array nums.
  • int next() Returns the next element in the array and moves the pointer to the next element.
  • bool hasNext() Returns true if there are still elements in the array.
  • int peek() Returns the next element in the array without moving the pointer.

 

Example 1:

Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]

Explanation
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // return 1, the pointer moves to the next element [1,2,3].
peekingIterator.peek();    // return 2, the pointer does not move [1,2,3].
peekingIterator.next();    // return 2, the pointer moves to the next element [1,2,3]
peekingIterator.next();    // return 3, the pointer moves to the next element [1,2,3]
peekingIterator.hasNext(); // return False

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • All the calls to next and peek are valid.
  • At most 1000 calls will be made to next, hasNext, and peek.

 

Follow up: How would you extend your design to be generic and work with all types, not just integer?
Accepted
137,170
Submissions
267,347
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
Think of "looking ahead". You want to cache the next element.
Show Hint 2
Is one variable sufficient? Why or why not?
Show Hint 3
Test your design with call order of peek() before next() vs next() before peek().
Show Hint 4
For a clean implementation, check out Google's guava library source code.

Average Rating: 4.83 (41 votes)

Premium

Solution


Overview - What is an Iterator?

Feel free to skip this section if you're already familiar with this material. We have included it, as this is a beginners question on iterators.

If you've heard of Iterators, you might assume they're simply a way of iterating over indexed or finite data structures. You've probably used them in loops, e.g. for item in items: in Python or for (int num : nums) in Java.

This may make it seem strange that we would need a .peek() on an Iterator. After all, couldn't we just convert our data structure into an array and use indexing to peek?

But actually Iterators have some interesting properties that make them widely useful for not only indexed collections (e.g. Array) and other finite data structures (e.g. LinkedList or HashMap keys), but also for (possibly-infinite) generated data. We'll look at an example of that soon.

The first property of an Iterator that we'll looked at is that it only needs to know how to get the next item. It doesn't need to store the entire data in memory if we don't need the entire data structure. For massive data structures, this is invaluable!

For example consider a linked list Iterator. We'll use Python as it's nice and compact. The same ideas apply to Java and C++:

class LinkedListIterator:
    def __init__(self, head):
        self._node = head

    def hasNext(self):
        return self._node is not None

    def next(self):
        result = self._node.value
        self._node = self._node.next
        return result

Notice how we store the head at the start, but as items are consumed, we discard the current one and replace it with the item in the node after?

This means that if we're simply iterating a Linked List, and don't ever need to go back to the head, then we only need to keep one value around at a time.

Another really interesting property of Iterators is that they can represent sequences without even using a data structure!

For example consider a range Iterator:

class RangeIterator:
    def __init__(self, min, max):
        self._max = max
        self._current = min

    def hasNext(self):
        return self._current < self._max

    def next(self):
        self._current += 1
        return self._current - 1

If we simply converted this to an Array, we'd need to allocate a large chunk of memory if min and max are far apart. For the most part, this would probably be wasted space.

However, by using an Iterator, we can use features like for i in range(40, 20000000) while still retaining the O(1)O(1) space of classic for (int i = min; i < max; i++) style loops seen in other languages.

Our final property is one that we couldn't even do by copying values into an Array—handling an infinite sequence. For example consider an Iterator of squares:

class SquaresIterator:
    def __init__(self):
        self._n = 0

    def hasNext(self):
        # It continues forever,
        # so definitely has a next!
        return True

    def next(self):
        result = self._n
        self._current += 1
        return result ** 2

Notice that because .hasNext() always returns True, this Iterator will never run out of items. And this is to be expected, there's always another square after the previous, so our Iterator can give as many as we ask from it.

Now that we've looked at why Iterators are awesome, let's consider what they are at a base level.

An Iterator only provides two methods:

  • .next() This returns the next item in the sequence. You can't assume that this item actually "exists" yet, it might be created when you call .next(), or it might already exist in a data structure that you have an Iterator over.

    Once .next() is called, it will update the state of the Iterator. This means once you've got a value from .next() you won't be able to get the same value again. Therefore, if you don't store or process the value you got from the Iterator then it's possibly gone forever!

  • .hasNext() This returns whether or not another item is available. For example, an array Iterator should return False if we're at the end of the array. But for an Iterator that can produce items indefinitely, such as our square generator above, it might never return False.

A further property of Iterators is that they provide a clean interface for the code using them. Without Iterators, Linked List's, for example, tend to be particularly messy, as the code for traversing them gets muddled within the application code. With an Iterator, the external code doesn't even know how the underlying data structure works. For all it knows, the data could be coming from a Linked List, an Array, a Tree, a State Machine, a clever number generator, a file reader, a robot sensor, etc.

Not having to deal with nodes, state, indexes, etc leads to clean code. We call this the Iterator Pattern, and it is one of the most important design patterns for a software engineer to know.

As shown above, with only two methods, we get a lot of benefit (e.g. infinite sequences) and increased performance (e.g. not expanding sequences like range into arrays). We also get a nice way of separating the underlying data structure from the code that uses it.



Approach 1: Saving Peeked Value

Intuition

Each time we call .next(...), a value is returned from the Iterator. If we call .next(...) again, a new value will be returned. This means that if we want to use a particular value multiple times, we had better save it.

Our .peek(...) method needs to call .next(...) on the Iterator. But because .next(...) will return a different value next time, we need to store the value we peeked so when .next(...) is called we return the correct value.

Algorithm

Complexity Analysis

  • Time Complexity : All methods: O(1)O(1).

    The operation performed to update our peeked value are all O(1)O(1).

    The actual operations from .next() are impossible for us to analyse, as they depend on the given Iterator. By design, they are none of our concern. Our addition to the time is only O(1)O(1) though.

  • Space Complexity : All methods: O(1)O(1).

    Like with time complexity, the Iterator itself is probably using memory in its own implementation. But again, this is not our concern. Our implementation only uses a few variables, so is O(1)O(1).



Approach 2: Saving the Next Value

Intuition

Instead of only storing the next value after we've peeked at it, we can store it immediately in the constructor and then again in the next(...) method. This greatly simplifies the code, because we no longer need conditionals to check whether or not we are currently storing a peeked at value.

Algorithm

Note that in the Java code, we need to be careful not to cause an exception to be thrown from the constructor, in the case that the Iterator was empty at the start. We can do this by checking it has a next, and if it doesn't, then we set the next variable to null.

Complexity Analysis

  • Time Complexity : All methods: O(1)O(1).

    Same as Approach 1.

  • Space Complexity : All methods: O(1)O(1).

    Same as Approach 1.



The Follow Up

For the most part, our code would work fine if we replaced integers with another data type (e.g. strings).

There is one case where this does not work, and that's if the underlying Iterator might return null/ None from .next(...) as an actual value. If our code is using null to represent an exhausted Iterator, or to represent that we don't currently have a peeked value stored away (as in Approach 1), then the conditionals in PeekingIterator will not behave as expected on these values coming out of the underlying Iterator.

We can solve it by using separate boolean variables to state whether or not there's currently a peeked value or the Iterator is exhausted, instead of trying to infer this information based on null status of value variables.

In Java, you can also use generics on your Iterator.


Report Article Issue

Comments: 9
Sithis's avatar
Read More

class PeekingIterator implements Iterator<Integer> {
    private final Iterator<Integer> iterator;
    private boolean hasPeeked;
    private Integer peekedElement;

    public PeekingIterator(Iterator<Integer> iterator) {
        this.iterator = iterator;
    }

    public Integer peek() {
        if (!hasPeeked) {
            hasPeeked = true;
            peekedElement = iterator.next();
        }
        return peekedElement;
    }

    @Override
    public Integer next() {
        if (!hasPeeked) {
            return iterator.next();
        }
        Integer result = peekedElement;
        peekedElement = null;
        hasPeeked = false;
        return result;
    }

    @Override
    public boolean hasNext() {
        return hasPeeked || iterator.hasNext();
    }
}

11
Show 1 reply
Reply
Share
Report
brostone51's avatar
Read More

Cheating with Python3 queue

from collections import deque

class PeekingIterator:
    q: deque = deque()
    
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        while iterator.hasNext():
            self.q.append(iterator.next())

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        return self.q[0]

    def next(self):
        """
        :rtype: int
        """
        return self.q.popleft()

    def hasNext(self):
        """
        :rtype: bool
        """
        return len(self.q) > 0

2
Show 2 replies
Reply
Share
Report
socram's avatar
Read More

I have a couple of comments on the "Follow up" for java:

  1. If the underlying Iterator returns null, then we can use Optional<Integer> to represent the last peeked value.

  2. I think that there is another case in which the proposed solution will not work properly: our PeekingIterator has private field that is a reference to the passed iterator, and if the caller of our function calls iterator.next() on the passed iterator after instantiating a PeekingIterator, then the we cannot guarantee the required behavior. The only solution to prevent this problem (IMHO) is to make a private copy of the values of the passed iterator and to use those. However, even this solution has a drawback, that is it will consume the passed iterator.

My solution with Optional:

import java.util.Optional;
import java.util.NoSuchElementException;

class PeekingIterator implements Iterator<Integer> {
    
    private final Iterator<Integer> iterator;
    private Optional<Integer> peeked = Optional.empty();
    
	public PeekingIterator(Iterator<Integer> iterator) {
	    this.iterator = iterator;	    
	}
	
    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
        if (hasNext()) {
            if (peeked.isPresent())
                return peeked.get();
            else {
                Integer val = iterator.next();
                peeked = Optional.ofNullable(val);
                return val;                
            }
        } else
            throw new NoSuchElementException();
	}
	
	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
        if (hasNext()) {
            if (peeked.isPresent()) {
                Integer val = peeked.get();
                peeked = Optional.empty();
                return val;
            } else
                return iterator.next();            
        } else 
            throw new NoSuchElementException();
	}
	
	@Override
	public boolean hasNext() {
	    return iterator.hasNext() || peeked.isPresent();
	}
}

1
Reply
Share
Report
ghaderi's avatar
Read More

It seems this part

    def next(self):
        result = self._n
        self._current += 1
        return result ** 2

Should be like this :

def next(self):
        result = self._n
        self._n += 1
        return result ** 2

The value of self._n needs to be updated after each next() call.

1
Reply
Share
Report
trimal's avatar
Read More

nitpick in python 3 range is not a iterator but it's a sequence
https://treyhunner.com/2018/02/python-range-is-not-an-iterator/
(list, tuple are also sequences but range gives answer computationally)

1
Reply
Share
Report
ZijiaqiXu's avatar
Read More

All parts are good except:
we don't need to throw the NSE exception explicitly, right? Because when you call iterator.next(), it will throw an NSE if there is no next element by its implementation. Below is my code, of a generalized form with a flag:

class PeekingIterator implements Iterator<Integer> {
    // saving peeked value
    // time: O(1)
    // memory: O(1)
    private Iterator<Integer> iterator;
    private boolean peeked;
    private Integer peekedValue;
    
	public PeekingIterator(Iterator<Integer> iterator) {
        this.iterator = iterator;
	}
	
	public Integer peek() {
        if (!peeked) {
            peekedValue = iterator.next();
            peeked = true;
        }
        return peekedValue;
	}
	
	@Override
	public Integer next() {
        if (peeked) {
            Integer toReturn = peekedValue;
            peeked = false;
            return toReturn;
        }
        
	    return iterator.next();
	}
	
	@Override
	public boolean hasNext() { 
	    return peeked || iterator.hasNext();
	}
}

0
Show 1 reply
Reply
Share
Report
michael206's avatar
Read More

should be an Easy

-5
Reply
Share
Report
zcoder_93's avatar
Read More

Python ~100% [1 min solution - Hacked it! :p ]

class PeekingIterator:
    START_INDEX = 0
    
    
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self.iterator = iterator

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        if len(self.iterator.v) > 0:
            return self.iterator.v[PeekingIterator.START_INDEX]

    def next(self):
        """
        :rtype: int
        """
        if len(self.iterator.v) > 0:
            return self.iterator.v.pop(PeekingIterator.START_INDEX)

    def hasNext(self):
        """
        :rtype: bool
        """
        return len(self.iterator.v) != 0

-1
Reply
Share
Report
rahulkun's avatar
Read More

python Iterator implementation is naive. Could you post C++ Iterator solution.

-5
Reply
Share
Report
Success
Details
Runtime: 4 ms, faster than 67.71% of C++ online submissions for Peeking Iterator.
Memory Usage: 7.3 MB, less than 99.45% of C++ online submissions for Peeking Iterator.
Next challenges:
Time Submitted
Status
Runtime
Memory
Language
06/10/2021 08:43Accepted4 ms7.3 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.